package cn.arnold.leetcode;

/**
 * @author Arnold-Xiang
 * @Info
 */
public class StringMatch {
    public static void main(String[] args) {
        String s = "aidslcocsi";
        String target = "coc";
        System.out.println(solution(s, target));
    }

    // KMP求解
    public static String solution(String s, String target) {
        char[] s_arr = s.toCharArray();
        char[] t_arr = target.toCharArray();
        int[] next = getNextArray(t_arr);
        int i = 0, j = 0;
        while (i < s_arr.length && j < t_arr.length) {
            if (j == -1 || s_arr[i] == t_arr[j]) {
                i++;
                j++;
            } else
                j = next[j];
        }
        String s1 = "";
        String s2 = "";
        int len = target.length();
        if (j == t_arr.length)
            s1 = s.substring(0, i - j);
        s2 = s.substring(i - j + 1 + len, s.length());
        return s1 + s2;
    }

    // 求出一个字符数组的next数组
    public static int[] getNextArray(char[] t) {
        int[] next = new int[t.length];
        next[0] = -1;
        next[1] = 0;
        int k;
        for (int j = 2; j < t.length; j++) {
            k = next[j - 1];
            while (k != -1) {
                if (t[j - 1] == t[k]) {
                    next[j] = k + 1;
                    break;
                } else {
                    k = next[k];
                }
                next[j] = 0;  //当k==-1而跳出循环时，next[j] = 0，否则next[j]会在break之前被赋值
            }
        }
        return next;
    }
}
